/**
 * Sort
 *
 * @author Darksiderl
 * @date 2018/2/27
 */
public class Sort {

    public static void main(String[] args) {

        int[] a = {1, 2, 3, 0, 44, 6, 21, 67};

        quickSort(a, 0, a.length - 1);

        for (int i : a) {
            System.out.println(i);
        }

    }

    public static int pardition(int[] a, int low, int high) {
        int i = low;
        int j = high;

        int privoteKey = a[low];

        while (i < j) {
            while (i < j && a[j] >= privoteKey) j--;
            swap(a, i, j);
            while (i < j && a[i] <= privoteKey) i++;
            swap(a, i, j);
        }

        return i;
    }

    public static void quickSort(int[] a, int low, int high) {

        if (low < high) {
            int privoteLoc = pardition(a, low, high);

            quickSort(a, low, privoteLoc - 1);
            quickSort(a, privoteLoc + 1, high);

        }

    }


    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
